interface TreeHelperConfig {
  id: string;
  children: string;
  pid: string;
}

// 默认配置
const DEFAULT_CONFIG: TreeHelperConfig = {
  id: 'id',
  children: 'children',
  pid: 'pid',
};

// 获取配置。  Object.assign 从一个或多个源对象复制到目标对象
const getConfig = (config: Partial<TreeHelperConfig>) => Object.assign({}, DEFAULT_CONFIG, config);

/**
 * 将列表转换为树形数据
 * @param list 列表数据
 * @param config 配置对象，可选，默认为空对象
 * @returns 转换后的树形数据
 */
export function listToTree<T = any>(list: any[], config: Partial<TreeHelperConfig> = {}): T[] {
  // 获取配置对象，并转换为 TreeHelperConfig 类型
  const conf = getConfig(config) as TreeHelperConfig;
  // 用于存储节点的 Map 对象
  const nodeMap = new Map();
  // 用于存储树形数据的数组
  const result: T[] = [];
  // 解构配置对象，获取 id、children 和 pid 的键名
  const { id, children, pid } = conf;

  // 遍历列表中的每个节点，将节点存储到 nodeMap 中，并初始化节点的 children
  for (const node of list) {
    node[children] = node[children] || [];
    nodeMap.set(node[id], node);
  }

  // 遍历列表中的每个节点，将节点添加到其父节点的 children 中或者添加到 result 中
  for (const node of list) {
    const parent = nodeMap.get(node[pid]);
    (parent ? parent[children] : result).push(node);
  }

  // 返回转换后的树形数据
  return result;
}

/**
 * 将树形数据转换为列表
 * @param tree 树形数据
 * @param config 配置对象，可选，默认为空对象
 * @returns 转换后的列表
 */
export function treeToList<T = any>(tree: any, config: Partial<TreeHelperConfig> = {}): T {
  // 获取配置对象
  config = getConfig(config);
  // 解构配置对象，获取子节点的键名
  const { children } = config;
  // 保存转换后的列表
  const result: any = [...tree];

  // 遍历列表中的每个节点
  for (let i = 0; i < result.length; i++) {
    // 如果节点没有子节点，则继续遍历下一个节点
    if (!result[i][children!]) continue;
    // 将子节点插入到当前节点之后的位置,splice() 函数接受三个参数：起始位置、删除元素个数和插入的元素。
    result.splice(i + 1, 0, ...result[i][children!]);
  }

  // 返回转换后的列表
  return result;
}

/**
 * 在树形数据中查找满足条件的节点
 * @param tree 树形数据
 * @param func 判断条件的回调函数
 * @param config 配置对象，可选，默认为空对象
 * @returns 找到的满足条件的节点，如果未找到则返回 null
 */
export function findNode<T = any>(
  tree: any,
  func: Fn,
  config: Partial<TreeHelperConfig> = {},
): T | null {
  // 获取配置对象，并转换为 TreeHelperConfig 类型
  config = getConfig(config);
  // 解构配置对象，获取 children 的键名
  const { children } = config;
  // 将树形数据转换为列表数据
  const list = [...tree];

  // 遍历列表中的每个节点，判断是否满足条件
  for (const node of list) {
    if (func(node)) return node; // 如果满足条件，直接返回节点
    node[children!] && list.push(...node[children!]); // 将节点的子节点添加到列表中
  }

  // 如果未找到满足条件的节点，返回 null
  return null;
}

/**
 * 在树形数据中查找所有满足条件的节点
 * @param tree 树形数据
 * @param func 判断条件的回调函数
 * @param config 配置对象，可选，默认为空对象
 * @returns 所有满足条件的节点组成的数组
 */
export function findNodeAll<T = any>(
  tree: any,
  func: Fn,
  config: Partial<TreeHelperConfig> = {},
): T[] {
  // 获取配置对象，并转换为 TreeHelperConfig 类型
  config = getConfig(config);
  // 解构配置对象，获取 children 的键名
  const { children } = config;
  // 将树形数据转换为列表数据
  const list = [...tree];
  // 存储所有满足条件的节点的数组
  const result: T[] = [];

  // 遍历列表中的每个节点，判断是否满足条件
  for (const node of list) {
    if (func(node)) result.push(node); // 如果满足条件，将节点添加到 result 数组中
    node[children!] && list.push(...node[children!]); // 将节点的子节点添加到列表中
  }

  // 返回所有满足条件的节点组成的数组
  return result;
}

/**
 * 在树形数据中查找满足条件的路径
 * @param tree 树形数据
 * @param func 条件判断函数，接收当前节点作为参数，并返回布尔值
 * @param config 配置对象，可选，默认为空对象
 * @returns 找到的路径或者 null
 */
export function findPath<T = any>(
  tree: any,
  func: Fn,
  config: Partial<TreeHelperConfig> = {},
): T | T[] | null {
  // 获取配置对象
  config = getConfig(config);
  // 保存当前路径的数组
  const path: T[] = [];
  // 将树形数据转换为列表
  const list = [...tree];
  // 保存已访问过的节点集合
  const visitedSet = new Set();
  // 解构配置对象，获取子节点的键名
  const { children } = config;

  // 遍历列表，直到列表为空
  while (list.length) {
    // 获取列表的第一个节点
    const node = list[0];
    if (visitedSet.has(node)) {
      // 如果节点已访问过，则删除当前路径中的最后一个节点及列表中的第1个节点
      path.pop();
      list.shift();
    } else {
      // 如果节点未访问过
      visitedSet.add(node);
      // 将子节点加入列表的开头
      node[children!] && list.unshift(...node[children!]);
      // 将当前节点加入路径
      path.push(node);
      if (func(node)) {
        // 如果当前节点满足条件，则返回路径
        return path;
      }
    }
  }

  // 如果没有找到满足条件的路径，则返回 null
  return null;
}

export function findPathAll(tree: any, func: Fn, config: Partial<TreeHelperConfig> = {}) {
  config = getConfig(config);
  const path: any[] = [];
  const list = [...tree];
  const result: any[] = [];
  const visitedSet = new Set(),
    { children } = config;
  while (list.length) {
    const node = list[0];
    if (visitedSet.has(node)) {
      path.pop();
      list.shift();
    } else {
      visitedSet.add(node);
      node[children!] && list.unshift(...node[children!]);
      path.push(node);
      func(node) && result.push([...path]);
    }
  }
  return result;
}

/**
 * 根据给定的过滤函数对树状结构进行遍历过滤，并返回过滤后的结果数组。
 * @param {T[]} tree 要过滤的树状结构数组
 * @param {(n: T) => boolean} func 过滤函数，接受一个树节点作为参数，返回一个布尔值表示是否保留该节点
 * @param {Partial<TreeHelperConfig>} [config = {}] 可选配置对象，包含可选的属性用于自定义过滤逻辑
 * @returns {T[]} 过滤后的结果数组
 */
export function filter<T = any>(
  tree: T[],
  func: (n: T) => boolean,
  // Partial 将 T 中的所有属性设为可选
  config: Partial<TreeHelperConfig> = {},
): T[] {
  // 获取配置
  config = getConfig(config);
  const children = config.children as string;

  function listFilter(list: T[]) {
    return (
      list
        //使用对象展开语法可以复制 node 对象的所有属性和值，并生成一个新的对象。这样做的目的是确保原始list不会被修改
        //({ ...node })是一个对象字面量，因为普通的对象字面量在 JavaScript 语法中和代码块语法非常相似。如果省略小括号，代码可能会被解释成一个块语句，这不是开发者想要的结果。
        //如果去掉({ ...node })中的小括号会出现语法错误。因为大括号被解释为了一个代码块语句，而 ...node 完全没有被绑定到一个对象上，无法正确地被解析。
        .map((node: any) => ({ ...node }))
        .filter((node) => {
          // 递归过滤子级节点
          node[children] = node[children] && listFilter(node[children]);
          // node符合条件或其子节点符合条件都被过滤出来
          return func(node) || (node[children] && node[children].length);
        })
    );
  }

  return listFilter(tree);
}

/**
 * 遍历树状结构的每一个节点，并对每个节点执行给定的函数。
 * @param {T[]} tree 要遍历的树状结构数组
 * @param {(n: T) => any} func 遍历函数，接受一个树节点作为参数，返回布尔值true可终止整个遍历过程
 * @param {Partial<TreeHelperConfig>} [config = {}] 可选配置对象，包含可选的属性用于自定义遍历逻辑
 * @returns {void}
 */
export function forEach<T = any>(
  tree: T[],
  func: (n: T) => any,
  config: Partial<TreeHelperConfig> = {},
): void {
  config = getConfig(config);
  const list: any[] = [...tree]; // 浅拷贝树节点数组
  const { children } = config;

  for (let i = 0; i < list.length; i++) {
    // 对当前节点执行遍历函数，若返回true时终止遍历
    // 当遍历大量节点时，此逻辑有助于避免无意义循环，减轻浏览器计算负担
    if (func(list[i])) {
      return;
    }
    // 若当前节点存在子级节点，则将子级节点插入到遍历队列中
    children && list[i][children] && list.splice(i + 1, 0, ...list[i][children]);
  }
}

/**
 * 使用提供的转换函数以递归方式映射树形结构数据。
 * 该函数遍历每一个节点，并对其调用一个转换函数，依此实现对整个树形结构的转换。
 *
 * @param treeData - 树形数据数组，每个元素代表树中的一个节点。
 * @param opt - 一个对象，包含两个属性:
 *      - children {string} [可选] 指定节点中子节点列表的属性名，默认为 'children'。
 *      - conversion {Fn} 转换函数，对每个节点进行转换的函数。
 * @returns 返回同类结构的新数组，该数组中的每个节点都经过了转换函数的处理。
 */
export function treeMap<T = any>(treeData: T[], opt: { children?: string; conversion: Fn }): T[] {
  // 使用 map 方法对数组中的每个元素执行操作
  return treeData.map((item) => {
    // 对单个节点应用 treeMapEach 函数，递归映射整个节点的树形结构
    return treeMapEach(item, opt);
  });
}

/**
 * 遍历树状数据，并执行转换函数conversion，返回转换后的数据。
 * @param {any} data 要遍历的树状数据
 * @param {Object} {children, conversion} 配置对象，包含子节点属性名和转换函数
 *   @property {string} [children = 'children'] 子节点属性名，默认为'children'
 *   @property {Fn} conversion 遍历的转换函数
 * @returns {Object} 转换后的数据
 */
export function treeMapEach(
  data: any,
  { children = 'children', conversion }: { children?: string; conversion: Fn },
) {
  // 判断当前节点是否有子节点
  const haveChildren = Array.isArray(data[children]) && data[children].length > 0;

  // 执行转换函数，将结果存储在conversionData中，若转换函数无返回值，则为{}
  const conversionData = conversion(data) || {};

  // 若当前节点有子节点，递归遍历子节点
  if (haveChildren) {
    return {
      ...conversionData,
      // 递归遍历子节点，并执行转换函数
      [children]: data[children].map((i: number) =>
        treeMapEach(i, {
          children,
          conversion,
        }),
      ),
    };
  } else {
    // 如果当前节点无子节点，直接返回当前节点的转换数据
    return {
      ...conversionData,
    };
  }
}

/**
 * 遍历树状数据，对每个节点执行指定的回调函数。
 * @param {any[]} treeDatas 要遍历的树状数据数组
 * @param {Fn} callBack 遍历时执行的回调函数，接收当前节点与其父节点作为参数
 * @param {Object} [parentNode = {}] 当前节点的父节点，默认为空对象
 * @returns {void}
 */
export function eachTree(treeDatas: any[], callBack: Fn, parentNode = {}) {
  // 遍历树状数据数组
  treeDatas.forEach((element) => {
    // 执行回调函数，传入当前节点与其父节点，若回调函数无返回值，则保留原节点
    const newNode = callBack(element, parentNode) || element;

    // 如果当前节点具有子节点，递归遍历子节点
    if (element.children) {
      eachTree(element.children, callBack, newNode);
    }
  });
}
